package queuerebuildbyheight406

import "sort"

// 题目链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/
// 思路：
// 1. 先创建一个空的队列
// 2. 将所有人按照身高从高到低排序，如果身高相同，则按照k值从小到大排序
// 3. 遍历所有人，将每个人插入到队列中，插入的位置为k值
// 4. 返回队列
// 5. 时间复杂度O(nlogn)，空间复杂度O(n)
func ReconstructQueue(people [][]int) [][]int {
	// 1. 先创建一个空的队列
	queue := make([][]int, 0)
	// 2. 将所有人按照身高从高到低排序，如果身高相同，则按照k值从小到大排序
	sort.Slice(people, func(i, j int) bool {
		if people[i][0] == people[j][0] {
			return people[i][1] < people[j][1]
		}
		return people[i][0] > people[j][0]
	})
	// 3. 遍历所有人，将每个人插入到队列中，插入的位置为k值，所以队列是从空队列一直膨胀到包含len(peple)个元素
	for _, person := range people {
		k := person[1]
		// newqueue = queue[0:k] + 当前元素 + queue[k:]
		queue = append(queue[:k], append([][]int{person}, queue[k:]...)...)
	}
	return queue
}
